#ifndef LEETCODE_CN_CPP_PROBLEMS_1268_H
#define LEETCODE_CN_CPP_PROBLEMS_1268_H

#include <algorithm>
#include <set>
#include <string>
#include <string_view>
#include <vector>

using namespace std;

namespace problem_1268
{

class Solution
{
public:
    vector<vector<string>> suggestedProducts(vector<string> &products, string searchWord)
    {
        set<string_view> prds;
        for (auto &product : products)
            prds.emplace(product);
        string tmp;
        vector<vector<string>> result;
        for (int i = 0; i < searchWord.size(); ++i)
        {
            result.emplace_back();
            tmp += searchWord[i];
            auto lower = prds.lower_bound(tmp);
            for (; lower != prds.end() && result.back().size() < 3; ++lower)
            {
                if (search(lower->begin(), lower->end(),
                           tmp.begin(), tmp.end()) != lower->begin())
                    break;
                result.back().emplace_back(*lower);
            }
        }
        return result;
    }
};

} // namespace problem_1268

#endif //LEETCODE_CN_CPP_PROBLEMS_1268_H
